package com.dyz.leetcode._16_dataStructureDesign;

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

public class _460_LFUCache {
    class Node{
        int key, val, count;
        Node next, prev;
        Node(){}
        Node(int key, int val, int count){
            this.key= key;
            this.val = val;
            this.count = count;
        }

    }
    class DoubleLinkedList {
        private Node head;
        private Node tail;

        DoubleLinkedList() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
        Node remove(Node node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
            return node;
        }

        //将node拼接到表尾
        void add(Node node){
            node.prev = tail.prev;
            tail.prev.next = node;
            node.next = tail;
            tail.prev  = node;
        }
        Node popFirst() {
            if (isEmpty()) {return null;}
            return remove(this.head.next);
        }

        boolean isEmpty() {
            return this.head.next == this.tail;
        }
    }


    private Map<Integer, Node> keyToNode;
    private Map<Integer, DoubleLinkedList> usedCountToKeys;
    private int capacity;
    // 记录整个缓存中所有 key 中使用最小的次数
    private int minUsedCount;
    public _460_LFUCache(int capacity) {
        keyToNode = new HashMap<>(capacity);
        usedCountToKeys = new HashMap<>();
        this.capacity = capacity;
        minUsedCount = 0;
    }

    public int get(int key) {
        // 注意：capacity 可能为 0
        if (capacity == 0) {return -1;}

        Node node = keyToNode.get(key);
        if(node==null){return -1;}
        // 维护这个 key 对应的 count
        int usedCount = node.count;
        // 1. 从这个 key 目前对应的 count 的集合中删除掉这个 key
        usedCountToKeys.get(usedCount).remove(node);
        node.count = usedCount + 1;
        // 2. 更新最小使用的次数
        // 如果当前的 usedCount 等于最小次数，
        // 并且当前的 usedCount 没有的 key，那么将最小次数加 1
        if (usedCount == minUsedCount
                && usedCountToKeys.get(usedCount).isEmpty()) {
            minUsedCount++;
        }

        // 3. 将 node 记录到 usedCount + 1 中的集合中
        putUsedCount(node, usedCount + 1);

        return node.val;
    }
    private void putUsedCount(Node node, int count) {
        if (!usedCountToKeys.containsKey(count)) {
            usedCountToKeys.put(count, new DoubleLinkedList());
        }
        usedCountToKeys.get(count).add(node);
    }

    public void put(int key, int value) {
            if (capacity == 0) {return;}

            if (keyToNode.containsKey(key)) {
                Node node = keyToNode.get(key);
                node.val = value;
                // 更新 key 对应的 value 值
                keyToNode.put(key, node);
                // 更新 key 对应的 count 值
                get(key);
                return;
            }

            if (keyToNode.size() == capacity) {
                // 删除最少使用的 key
                Node removeNode = usedCountToKeys.get(minUsedCount).popFirst();
                keyToNode.remove(removeNode.key);
            }

            // 新增一个缓存中不存在的 key
            Node node = new Node(key, value, 1);
            keyToNode.put(key, node);

            // 将 key 记录到 minUsedCount 中的集合中
            minUsedCount = 1;
            putUsedCount(node, minUsedCount);
        }

}
